package com.leetcode.study;

/**
 * https://leetcode.cn/problems/binary-search/description/
 *
 * 二分查找，时间复杂度O(log n)
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 * 你可以假设 nums 中的所有元素是不重复的。
 * n 将在 [1, 10000]之间。
 * nums 的每个元素都将在 [-9999, 9999]之间。
 *
 */
public class L704 {


    public static void main(String[] args) {

        int[] array = {-1, 0, 3, 5, 9, 12};

        int target = 9;

        System.out.println(baseSearch(array, target));
        System.out.println(search1(array, target));
        System.out.println(search2(array, target));
    }


    /**
     * 基础版本二分查找，查找范围左闭右闭区间
     * @param nums
     * @param target
     * @return
     */
    public static int baseSearch(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        while (i <= j) {
            // 为什么不除2，而采用无符号右移1位，超出整数的最大范围时，/2会导致负数
            int mid = (i + j) >>> 1;
            if (target < nums[mid]) {
                j = mid - 1;

            } else if (nums[mid] < target) {
                i = mid + 1;

            } else {
                return mid;
            }
        }
        return -1;
    }


    /**
     * 改进版本，查找范围左闭右开区间
     * @param nums
     * @param target
     * @return
     */
    public static int search1(int[] nums, int target) {
        int i = 0, j = nums.length;

        while (i < j) {
            int mid = (i + j) >>> 1;

            if (target < nums[mid]) {
                j = mid;

            } else if (nums[mid] < target) {
                i = mid + 1;

            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 平衡版，查找范围左闭右开区间，先缩小范围，当比较范围等于1时，证明比较完了，再比较返回值
     * @param nums
     * @param target
     * @return
     */
    public static int search2(int[] nums, int target) {
        int i = 0, j = nums.length;

        while (1 < j - i) {
            int mid = (i + j) >>> 1;

            if (target < nums[mid]) {
                j = mid;

            }  else {
                i = mid;
            }
        }

        if (nums[i] == target) {
            return i;
        }
        return -1;
    }
}
